// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

// impl ListNode {
//     #[inline]
//     fn new(val: i32) -> Self {
//         ListNode { next: None, val }
//     }
// }

struct Solution;

impl Solution {
    // a - b - c

    pub fn swap_nodes(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        // 链长度不为0
        let mut head = head.unwrap();
        let mut cur = head.as_mut();
        let mut link1_cur;
        let mut link2_cur;

        let mut link1 = None;
        let mut link2 = None;
        let mut len = 1;
        while let Some(next) = cur.next.as_mut() {
            cur = next;
            len += 1;
        }

        if len != 1 {
            let right = len - k + 1;
            if right != k {
                // 只交换头部和尾部特殊处理
                if k == 1 {
                    std::mem::swap(&mut head.next, &mut link1);
                    if len < 3 {
                        // 长度只有2需要处理
                        link1.as_mut().unwrap().next = Some(head);
                        return link1;
                    } else {
                        let mov = len - 3;
                        link1_cur = link1.as_mut().unwrap();
                        for _ in 0..mov {
                            link1_cur = link1_cur.next.as_mut().unwrap();
                        }
                        let mut head = Some(head);
                        std::mem::swap(&mut link1_cur.next, &mut head);
                        head.as_mut().unwrap().next = link1;
                        return head;
                    }
                } else {
                    // 只有操作不同的节点才需要操作
                    cur = head.as_mut();

                    for _ in 1..(k - 1) {
                        cur = cur.next.as_mut().unwrap();
                    }
                    // 把需要交换的那个数（之后叫左数）和后面链截取到link1
                    std::mem::swap(&mut cur.next, &mut link1);
                    // 把左数后面的链截取到link2
                    link1_cur = link1.as_mut().unwrap();
                    std::mem::swap(&mut link1_cur.next, &mut link2);

                    // 把左数交换到应该到的地方
                    link2_cur = link2.as_mut().unwrap();
                    if (len - k + 1) < (k + 2) {
                        std::mem::swap(&mut link1, &mut link2);
                    } else {
                        for _ in (k + 2)..(len - k + 1) {
                            link2_cur = link2_cur.next.as_mut().unwrap();
                        }
                        std::mem::swap(&mut link2_cur.next, &mut link1);
                    }

                    // 把右数后面交换到应该到的地方
                    link2_cur = link2.as_mut().unwrap();
                    while link2_cur.next.is_some() {
                        link2_cur = link2_cur.next.as_mut().unwrap();
                    }
                    link1_cur = link1.as_mut().unwrap();
                    std::mem::swap(&mut link2_cur.next, &mut link1_cur.next);

                    // 拼接
                    link1_cur = link1.as_mut().unwrap();
                    while link1_cur.next.is_some() {
                        link1_cur = link1_cur.next.as_mut().unwrap();
                    }
                    link1_cur.next = link2;
                    if head.next.is_some() {
                        let mut head_cur = head.next.as_mut().unwrap();
                        while head_cur.next.is_some() {
                            head_cur = head_cur.next.as_mut().unwrap();
                        }
                        head_cur.next = link1;
                    } else {
                        head.next = link1;
                    }
                }
            }
        }

        Some(head)
    }
}

fn main() {
    Solution::swap_nodes(None, 0);
}
